package 数据结构专栏.A_二叉树专栏;

import java.util.ArrayList;

/**
 * @DESC 定义最大二叉树
 * 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
 * <p>
 * 二叉树的根是数组中的最大元素。
 * 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 * 右子树是通过数组中最大值右边部分构造出的最大二叉树。
 * 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-binary-tree
 * <p>
 * <p>
 * 树的递归很多时候都可以套路解决，就一个模版，递归套路三部曲：
 * 找终止条件：当l>r时，说明数组中已经没元素了，自然当前返回的节点为null。
 * 每一级递归返回的信息是什么：返回的应该是当前已经构造好了最大二叉树的root节点。
     * 一次递归做了什么：找当前范围为[l,r]的数组中的最大值作为root节点，然后将数组划分成[l,bond-1]和[bond+1,r]两段，并分别构造成root的左右两棵子最大二叉树。
 * @Author tzq
 * @Date 2020-04-03 10:09
 **/
public class _654_最大二叉树 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 6, 0, 5};
        TreeNode treeNode = new _654_最大二叉树().constructMaximumBinaryTree(arr);
        ArrayList<Integer> list = TreeNode.printFromTopToBottom(treeNode);
        System.out.println(list);

    }
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return maxTree(nums, 0, nums.length - 1);
    }

    public TreeNode maxTree(int[] nums, int l, int r) {
        //1. 判断边界条件 当左边大于右边的时候返回NULL；
        if (l > r) return null;
        //2. 找出最大值索引值
        int maxIndex = findMaxIndex(nums, l, r);
        //3.以最大值新建树顶
        TreeNode root = new TreeNode(nums[maxIndex]);
        //4.分别递归左右子树
        root.left = maxTree(nums, l, maxIndex - 1);
        root.right = maxTree(nums, maxIndex + 1, r);
        //5.返回根节点
        return root;
    }

    public int findMaxIndex(int[] nums, int l, int r) {
        // 初始化最小值和最小index
        int max = Integer.MIN_VALUE, maxIndex = l;
        // 注意这里的遍历的起点和终点的判断条件
        for (int i = l; i <= r; i++) {
            if (max < nums[i]) {
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

